#ifndef __LISTA_H__
#define __LISTA_H__

#ifndef NULL
#define NULL 0
#endif

#include <iostream>
#include <cassert>
#include "defines.h"
using namespace std;

template<class T> //se puede asumir que el tipo T tiene constructor por copia
class Lista {
	private:

		class Nodo{
		public:
				Nodo();
				bool esVacia() const;
				Nodo(const T& p_valor, Nodo* p_anterior, Nodo* p_proximo);
				T valor;
				Nodo* anterior;
				Nodo* proximo;
		};

	public:

		class IterLista {
			public:
				IterLista();
				IterLista(Lista* l);
				~IterLista();
				T& actual() const;
				void irAlUlt();
				void eliminar();
				bool tieneProximo() const;
				void avanzar();
				Lista& lista() const;
			private:
				Nodo* nodo;
				Lista* l;
		};

		class IterLista_const {
			public:
				IterLista_const();
				IterLista_const(const Lista* l);
				~IterLista_const();
				const T& actual() const;
				bool tieneProximo() const;
				void avanzar();
				const Lista& lista() const;
			private:
				Nodo* nodo;
				const Lista* l;
		};

		/*constructor por defecto, con la lista vacia*/
		Lista();

		/*constructor por copia*/
		Lista(const Lista&);

		/*Destructor. Liberar toda la memoria!*/
		~Lista();

		/*Inserta el elemento a la izquierda de la lista*/
		void agregar(const T e);

		/*Dice si la lista es vacia. Cuidado! Esta funcion debe ser mas
		 *eficiente que longitud*/
		bool esVacia() const;

		/*Devuelve el elemento de mas a la izquierda de la lista*/
		const T& primero() const;

		/*Devuelve el elemento de mas a la derecha de la lista*/
		T& ultimo() const;

		/*Inserta el elemento a la derecha de la lista*/
		void agregarAtras(const T e);

		/*Dice cuantos elementos tiene la lista*/
		int longitud() const;

		/*Dice el elemento parametro esta o no esta en la lista*/
		bool esta(const T e) const;

	   	 /*Devuelve el iesimo elemento de la lista*/
		T iesimo(const int i) const;

		/*Devuelve un iterador al principio de la lista*/
		IterLista crearIt();

		/*Devuelve un iterador al ultimo de la lista*/
		IterLista crearItAlUlt();

		/*Devuelve un iterador const al principio de la lista*/
		IterLista_const crearIt_const() const;

		/*Muestra la lista en formato [e1,e2,...,en] por el stream que recibe
		 *como parametro. La lista vacia se muestra como [] y una lista
		 *con un solo elemento e como [e]*/
		void mostrarLista(ostream&) const;

		/*Operador de asignacion. Copia una lista igual al parametro.
		 *Borra todo lo que hubiese originalmente.*/
		Lista& operator=(const Lista&);

		/* Operador de igualdad. Lo uso en los tests */
		bool operator==(const Lista&) const;

		/* Operador de desigualdad. Lo uso en los tests */
		bool operator!=(const Lista&) const;

	private:

		Nodo* _primero;
		Nodo* _ultimo;
		int l;//longitud

		/*Elimina el elemento de mas a la derecha de la lista*/
		void eliminarDesdeLaDerecha();

		/*Vacia la lista*/
		void vaciar();

		/*Copia una lista. En realidad, si no es vacia, le concatena una copia atras*/
		void copiar(const Lista&);
};

/******************************************************************************************/
/*                                  FUNCIONES DE Lista                                    */
/******************************************************************************************/


template<typename T>
Lista<T>::Lista():_primero(NULL),_ultimo(NULL),l(0){}

template<typename T>
Lista<T>::Lista(const Lista& l):_primero(NULL),_ultimo(NULL),l(0){
	copiar(l);
}

template<typename T>
Lista<T>::~Lista(){
	vaciar();
}

template<typename T>
void Lista<T>::agregar(const T e){
    if(l==0){
        _primero=new Nodo(e,NULL,NULL);
        _ultimo=_primero;
    }else{
        _primero=new Nodo(e,NULL,_primero);
        _primero->proximo->anterior=_primero;
    }
    l++;
}

template<typename T>
bool Lista<T>::esVacia() const{
    return l==0;
}

template<typename T>
const T& Lista<T>::primero() const{
    assert(!(*this).esVacia()); // Me aseguro que cumpla la precondicion
    return _primero->valor;
}

template<typename T>
T& Lista<T>::ultimo() const{
    assert(!(*this).esVacia()); // Me aseguro que cumpla la precondicion
    return _ultimo->valor;
}

template<typename T>
void Lista<T>::agregarAtras(const T e){
    if(l==0){
        _ultimo=new Nodo(e,NULL,NULL);
        _primero=_ultimo;
    }else{
        _ultimo=new Nodo(e,_ultimo,NULL);
        _ultimo->anterior->proximo=_ultimo;
    }
    l++;
}

template<typename T>
int Lista<T>::longitud() const{
    return l;
}

template<typename T>
bool Lista<T>::esta(const T e) const{
	bool res = false;
	Nodo* actual = _primero;
	while(actual!=NULL && !res){
		if(actual->valor == e){
			res = true;
		}
		actual = actual->proximo;
	}
	return res;
}

template<typename T>
T Lista<T>::iesimo(const int i) const{
    assert(i<(*this).l && i>=0); // Me aseguro que cumpla la precondicion
	int j = 0;
	Nodo* pos = _primero;
	while(j < i){
		pos = (*pos).proximo;
		j++;
	}
	return (*pos).valor;
}

template<typename T>
typename Lista<T>::IterLista Lista<T>::crearIt(){
	return IterLista(this);
}

template<typename T>
typename Lista<T>::IterLista Lista<T>::crearItAlUlt(){
	typename Lista<T>::IterLista it = IterLista(this);
	it.irAlUlt();
	return it;
}

template<typename T>
typename Lista<T>::IterLista_const Lista<T>::crearIt_const() const{
	return IterLista_const(this);
}

template<typename T>
void Lista<T>::mostrarLista(ostream& out) const{
    out << '[';
    Nodo* aux=_primero;
    while(aux){
        out<<aux->valor;
        aux=aux->proximo;
        if(aux)out<<',';
    }
    out << ']';
}

template<typename T>
Lista<T>& Lista<T>::operator=(const Lista<T>& l){
	if(this != &l){ // Que no vaya a ser la misma lista, sino explota!
		vaciar();
		copiar(l);
	}
	return *this;
}

template<typename T>
bool Lista<T>::operator==(const Lista<T>& l) const{
    Nodo* actual = _primero;
    typename Lista<T>::IterLista_const it = l.crearIt_const();
    while(actual && it.tieneProximo()){
        if(actual->valor != it.actual()){ // comparo elemento a elemento
            return false;
        }
        actual = actual->proximo;
        it.avanzar();
    }
    if(actual || it.tieneProximo()) return false; // me fijo si alguno era mas largo
    return true; // si llegue hasta aca son iguales
}

template<typename T>
bool Lista<T>::operator!=(const Lista<T>& l) const{
    return !(*this==l);
}

template<typename T>
void Lista<T>::eliminarDesdeLaDerecha(){
    assert(l>0); // Me aseguro que cumpla la precondicion
    if(l==1){
        delete _ultimo;
        _ultimo=_primero=NULL;
    }else{
        _ultimo=_ultimo->anterior;
        delete _ultimo->proximo;
        _ultimo->proximo=NULL;
    }
    l--;
}

template <typename T>
void Lista<T>::vaciar(){
	while(_primero){
		eliminarDesdeLaDerecha();
	}
}

template <typename T>
void Lista<T>::copiar(const Lista<T>& l){
	Nodo* aux = l._primero;
	while(aux){
		agregarAtras(aux->valor);
		aux = aux->proximo;
	}
}

/******************************************************************************************/
/*                                FUNCIONES DE IterLista                                  */
/******************************************************************************************/

template<typename T>
Lista<T>::IterLista::IterLista() : nodo(NULL), l(NULL) {}

template<typename T>
Lista<T>::IterLista::IterLista(Lista<T>* _l) : nodo(_l->_primero), l(_l) {}

template<typename T>
Lista<T>::IterLista::~IterLista(){}

template<typename T>
T& Lista<T>::IterLista::actual() const{
	assert(nodo!=NULL); // Me aseguro que cumpla la precondicion
	return nodo->valor;
}

template<typename T>
void Lista<T>::IterLista::eliminar(){
    assert(nodo!=NULL); // Me aseguro que cumpla la precondicion
    Nodo* aux = nodo;

    if(nodo->anterior != NULL){
	    // Si no es el primero
	    (nodo->anterior)->proximo = nodo->proximo;
    }else{
        // Si es el primero
        l->_primero = nodo->proximo;
      //  (l->_primero)->anterior = NULL;
    }

    if(nodo->proximo != NULL){
        // Si no es el ultimo
        (nodo->proximo)->anterior = nodo->anterior;
    }else{
        // Si es el ultimo
        l->_ultimo = nodo->anterior;
    //    (l->_ultimo)->proximo = NULL; 
    }

    nodo = aux->proximo;
    delete aux;
    (l->l)--; // falta en la spec!
}

template<typename T>
bool Lista<T>::IterLista::tieneProximo() const{
	return nodo != NULL; // esto esta mal en la spec!!!
}

template<typename T>
void Lista<T>::IterLista::avanzar(){
    assert(nodo!=NULL); // Me aseguro que cumpla la precondicion
	nodo = nodo->proximo;
}

template<typename T>
void Lista<T>::IterLista::irAlUlt(){
	nodo = l->_ultimo;
}

template<typename T>
Lista<T>& Lista<T>::IterLista::lista() const{
	return *l;
}

/******************************************************************************************/
/*                             FUNCIONES DE IterLista_const                               */
/******************************************************************************************/

template<typename T>
Lista<T>::IterLista_const::IterLista_const() : nodo(NULL), l(NULL) {}

template<typename T>
Lista<T>::IterLista_const::IterLista_const(const Lista<T>* _l) : nodo(_l->_primero), l(_l) {}

template<typename T>
Lista<T>::IterLista_const::~IterLista_const(){}

template<typename T>
const T& Lista<T>::IterLista_const::actual() const{
	assert(nodo!=NULL); // Me aseguro que cumpla la precondicion
	return nodo->valor;
}

template<typename T>
bool Lista<T>::IterLista_const::tieneProximo() const{
	return nodo != NULL; // esto esta mal en la spec!!!
}

template<typename T>
void Lista<T>::IterLista_const::avanzar(){
    assert(nodo!=NULL); // Me aseguro que cumpla la precondicion
	nodo = nodo->proximo;
}

template<typename T>
const Lista<T>& Lista<T>::IterLista_const::lista() const{
	return *l;
}

/******************************************************************************************/
/*                                   FUNCIONES DE Nodo                                    */
/******************************************************************************************/

template<typename T>
Lista<T>::Nodo::Nodo(){
	anterior = NULL;
	proximo = NULL;
}

template<typename T>
Lista<T>::Nodo::Nodo(const T& p_valor, Nodo* p_anterior, Nodo* p_proximo) : valor(p_valor), anterior(p_anterior), proximo(p_proximo){}

/******************************************************************************************/
/*                                         OTRAS                                          */
/******************************************************************************************/

template<class T>
ostream& operator<<(ostream& out, const Lista<T>& l) {
	l.mostrarLista(out);
	return out;
}

#endif
